package sorting;

import util.Util;

public class sort {

	/**
	 * @param args
	 */
	public static void main(String[] args) {
		
		int[] intArray = {5,6,3,7,8,3,2,22,4,6};

		mergeSort(intArray);
		System.out.println(Util.collectionToString(intArray));
	}


	public static void mergeSort(int[] array)
	{
		int[] temp = new int[array.length];	
		mergeSort(array, temp, 0, array.length-1);
	}
	private static void mergeSort(int[] array, int[] temp, int left, int right)
	{
		if(right<=left)
		{
			return;
		}
		int mid = (left + right) / 2;
		mergeSort(array, temp, left, mid);
		mergeSort(array, temp, mid+1, right);	
		merge(array, temp, left, mid, right);
	}
	// merge elements within array in the specified range, left and right
	private static void merge(int[] array, int[] temp, int left, int mid,  int right)
	{
		int tempIndex = left;
		int lCursor = left;
		int rCursor = mid + 1;
		while(tempIndex <= right)
		{
			// no comparism just straight copy
			if(lCursor > mid)
			{
				temp[tempIndex] = array[rCursor++];
			}
			else if (rCursor > right)
			{
				temp[tempIndex] = array[lCursor++];
			}
			// compare the two groups, copy over the smaller one, increment cursor on the group that got copied over
			else
			{
				temp[tempIndex] = (array[lCursor] < array[rCursor]) ? array[lCursor++] : array[rCursor++];
			}
			tempIndex++;
		}
		// copy back to original array
		for(int j = left ; j<=right ; j++)
		{
			array[j] = temp[j];
		}
	}


	public void quickSort()
	{

	}

	public void bucketSort()
	{

	}

	public void radixSort()
	{

	}
}
